/*
** Xin YUAN, 2023, BSD (2)
*/

////////////////////////////////////////////////////////////////////////////////
#ifndef __CTL_COLLB_H__
#define __CTL_COLLB_H__
////////////////////////////////////////////////////////////////////////////////

#ifndef __CTL_DEF_H__
	#error collb.h requires def.h to be included first.
#endif

////////////////////////////////////////////////////////////////////////////////
namespace CTL {
////////////////////////////////////////////////////////////////////////////////

#pragma pack(push, 1)

// PlainArray<T>

class _plain_array_base
{
protected:
	struct _header
	{
		uintptr_t bytes_per_element;
		uintptr_t size;
		uintptr_t allocate_size;
	};

protected:
	_plain_array_base() noexcept : m_p(nullptr)
	{
	}
	_plain_array_base(const _plain_array_base&) = delete;
	_plain_array_base(_plain_array_base&& src) noexcept : m_p(src.m_p)
	{
		src.m_p = nullptr;
	}
	~_plain_array_base() noexcept
	{
		dump();
	}

	_plain_array_base& operator=(const _plain_array_base&) = delete;
	_plain_array_base& operator=(_plain_array_base&& src) noexcept
	{
		if ( this != &src ) {
			if ( m_p == src.m_p ) {
				assert( m_p == nullptr );
			}
			else {
				dump();
				m_p = src.m_p;
				src.m_p = nullptr;
			}
		}
		return *this;
	}

	void dump() noexcept
	{
		if ( m_p != nullptr ) {
			AllocatorTraits::Free(m_p);
			m_p = nullptr;
		}
	}

	uintptr_t get_size() const noexcept
	{
		return m_p == nullptr ? 0 : get_header()->size;
	}

	const void* get_at(uintptr_t index) const noexcept
	{
		return (uint8_t*)get_data() + index * get_header()->bytes_per_element;
	}
	void* get_at(uintptr_t index) noexcept
	{
		return (uint8_t*)get_data() + index * get_header()->bytes_per_element;
	}

	bool set_size(uintptr_t bytes_per_element, uintptr_t count) noexcept
	{
		_header* ph = get_header();
		uintptr_t old_alloc = 0;
		if ( ph != nullptr )
			old_alloc = ph->allocate_size;
		if ( count <= old_alloc ) {
			if ( ph != nullptr )
				ph->size = count;
			return true;
		}
		uintptr_t add_count = old_alloc / 8;
		if ( add_count == 0 )
			add_count = 4;
		else if ( add_count > 1024 )
			add_count = 1024;
		uintptr_t new_alloc;
		if ( !ArithmeticTraits<uintptr_t>::Add(old_alloc, add_count, new_alloc) )
			return false;
		if ( count > new_alloc )
			new_alloc = count;
		uintptr_t bytes;
		if ( !ArithmeticTraits<uintptr_t>::Multiply(new_alloc, bytes_per_element, bytes) )
			return false;
		if ( !ArithmeticTraits<uintptr_t>::Add(bytes, (uintptr_t)sizeof(_header), bytes) )
			return false;
		void* pn = AllocatorTraits::Reallocate(m_p, bytes);
		if ( pn == nullptr )
			return false;
		m_p = pn;
		get_header()->bytes_per_element = bytes_per_element;
		get_header()->allocate_size = new_alloc;
		get_header()->size = count;
		return true;
	}
	bool insert_at(uintptr_t bytes_per_element, uintptr_t index, uintptr_t count = 1) noexcept
	{
		assert( count > 0 );
		uintptr_t old_size = get_size();
		uintptr_t new_size = 0;
		if ( index < old_size )
			new_size = old_size + count;
		else
			new_size = index + count;
		if ( new_size < count )
			return false;
		if ( !set_size(bytes_per_element, new_size) )
			return false;
		if ( index < old_size )
			MemoryTraits::Move(get_at(index), (old_size - index) * bytes_per_element, get_at(index + count));
		return true;
	}
	void remove_at(uintptr_t index, uintptr_t count = 1) noexcept
	{
		assert( count > 0 );
		uintptr_t size = get_size();
		uintptr_t cut = index + count;
		assert( cut >= count && cut <= size );
		MemoryTraits::Move(get_at(cut), (size - cut) * get_header()->bytes_per_element, get_at(index));
		get_header()->size -= count;
	}

	bool append(uintptr_t bytes_per_element, uintptr_t count = 1) noexcept
	{
		return insert_at(bytes_per_element, get_size(), count);
	}

	void shrink() noexcept
	{
		_header* ph = get_header();
		if ( ph == nullptr )
			return ;
		uintptr_t size = ph->size;
		assert( size <= ph->allocate_size );
		if ( size == ph->allocate_size )
			return ;
		if ( size == 0 ) {
			dump();
			return ;
		}
		uintptr_t bytes = ph->bytes_per_element * size + sizeof(_header);
		void* pn = AllocatorTraits::Reallocate(m_p, bytes);
		if ( pn == nullptr )
			return ;
		m_p = pn;
		get_header()->allocate_size = size;
	}

protected:
	const _header* get_header() const noexcept
	{
		return (const _header*)m_p;
	}
	_header* get_header() noexcept
	{
		return (_header*)m_p;
	}
	const void* get_data() const noexcept
	{
		return (const void*)(get_header() + 1);
	}
	void* get_data() noexcept
	{
		return (void*)(get_header() + 1);
	}

protected:
	void* m_p;
};

template <typename T>
class PlainArray : public _plain_array_base
{
private:
	typedef _plain_array_base  baseClass;

public:
	PlainArray() noexcept
	{
	}
	PlainArray(const PlainArray&) = delete;
	PlainArray(PlainArray&& src) noexcept : baseClass(rv_forward(static_cast<baseClass&>(src)))
	{
	}
	~PlainArray() noexcept
	{
	}

	PlainArray& operator=(const PlainArray&) = delete;
	PlainArray& operator=(PlainArray&& src) noexcept
	{
		baseClass::operator=(rv_forward(static_cast<baseClass&>(src)));
		return *this;
	}

	bool IsNull() const noexcept
	{
		return get_header() == nullptr;
	}
	bool IsEmpty() const noexcept
	{
		return GetSize() == 0;
	}

	uintptr_t GetSize() const noexcept
	{
		return get_size();
	}

	const T* GetAddress() const noexcept
	{
		return (const T*)get_data();
	}
	T* GetAddress() noexcept
	{
		return (T*)get_data();
	}
	const T& GetAt(uintptr_t index) const noexcept
	{
		assert( index < get_size() );
		return *((const T*)get_at(index));
	}
	T& GetAt(uintptr_t index) noexcept
	{
		assert( index < get_size() );
		return *((T*)get_at(index));
	}

	const T& operator[](uintptr_t index) const noexcept
	{
		return GetAt(index);
	}
	T& operator[](uintptr_t index) noexcept
	{
		return GetAt(index);
	}

	void Clear() noexcept
	{
		dump();
	}

	bool SetSize(uintptr_t count) noexcept
	{
		return set_size(sizeof(T), count);
	}
	bool InsertAt(uintptr_t index, uintptr_t count = 1) noexcept
	{
		return insert_at(sizeof(T), index, count);
	}
	void RemoveAt(uintptr_t index, uintptr_t count = 1) noexcept
	{
		return remove_at(index, count);
	}
	bool Append(uintptr_t count = 1) noexcept
	{
		return append(sizeof(T), count);
	}

	void Shrink() noexcept
	{
		shrink();
	}
};

#pragma pack(pop)

// ArrayHelper

class ArrayHelper
{
public:
	// binary search
	/*! \brief Search an element using binary method.

	Search an element using binary method.
	\param p [in] A pointer to array.
	\param size [in] The size of array.
	\param val [in] Specify the keyword.
	\param result [out] If the return value is true, this variable receives the position of that element.
	                    If the return value is false, this variable receives the position at which the element can be inserted.
	\return true means the specified element is found, false means otherwise.
	*/
	template <typename T, class TCompareTrait = DefaultCompareTrait<T>>
	static bool BinarySearch(const T* p, uintptr_t size, const T& val, uintptr_t& result) noexcept
	{
		result = 0;
		// [0, size)
		uintptr_t right = size;
		if ( right == 0 )
			return false;
		uintptr_t left = 0;
		while ( left < right ) {
			uintptr_t mid = left + (right - left) / 2;  // if we use (left + right) / 2, it may overflow
			if ( TCompareTrait::IsEQ(*(p + mid), val) ) {
				result = mid;
				return true;
			}
			if ( TCompareTrait::IsLT(*(p + mid), val) )
				left = mid + 1;
			else
				right = mid;
		}
		result = left;
		return false;
	}
	template <typename T, class TCompareTrait = DefaultCompareTrait<T>>
	static bool BinarySearchFirst(const T* p, uintptr_t size, const T& val, uintptr_t& result) noexcept
	{
		if ( !BinarySearch(p, size, val, result) )
			return false;
		uintptr_t prev = result;
		while ( prev > 0 ) {
			-- prev;
			if ( TCompareTrait::IsNE(*(p + prev), val) )
				break;
			result = prev;
		}
		return true;
	}
};

// CyclicQueueUtility
/*! \brief A utility class for cyclic queue.

A utility class for cyclic queue.
\tparam T The type of size & index.
*/
template <typename T>
class CyclicQueueUtility
{
public:
	/*! \brief Constructor.

	Constructor.
	*/
	explicit CyclicQueueUtility(T capacity = 0) noexcept : m_capacity(capacity), m_front(0), m_rear(0)
	{
	}
	//bit-copy

	/*! \brief Set the capacity of queue.

	Set the capacity of queue.
	\param capacity [in] Specify the new capacity. This value must be not less than 2.
	*/
	void SetCapacity(T capacity) noexcept
	{
		assert( capacity >= 2 );
		m_capacity = capacity;
	}
	/*! \brief Get the capacity of queue.

	Get the capacity of queue.
	\return A value for capacity.
	*/
	T GetCapacity() const noexcept
	{
		return m_capacity;
	}

	/*! \brief Clear the queue.

	Clear the queue to empty.
	*/
	void Clear() noexcept
	{
		m_front = m_rear = 0;
	}
	T GetFront() const noexcept
	{
		return m_front;
	}
	T GetRear() const noexcept
	{
		return m_rear;
	}

	void SetFront(T index) noexcept
	{
		m_front = index;
	}
	void SetRear(T index) noexcept
	{
		m_rear = index;
	}

	/*! \brief Check if the queue is empty.

	Check if the queue is empty.
	\return true for empty, false for otherwise.
	*/
	bool IsEmpty() const noexcept
	{
		return m_front == m_rear;
	}
	/*! \brief Check if the queue is full.

	Check if the queue is full.
	\return true for full, false for otherwise.
	*/
	bool IsFull() const noexcept
	{
		return IsFront(CalcNext(m_rear));
	}

	bool IsFront(T index) const noexcept
	{
		return index == m_front;
	}

	/*! \brief Get the number of valid elements in current queue.

	Get the number of valid elements in current queue.
	\return The number of valid elements.
	*/
	T GetSize() const noexcept
	{
		return (m_rear - m_front + m_capacity) % m_capacity;
	}

	/*! \brief Calculate the index of the next element.

	Calculate the index of the next element.
	\param index [in] Specify the index.
	\return The next element index.
	*/
	T CalcNext(T index) const noexcept
	{
		return (index + 1) % m_capacity;
	}

	T En() noexcept
	{
		T temp = m_rear;
		m_rear = CalcNext(m_rear);
		return temp;
	}
	T De() noexcept
	{
		T temp = m_front;
		m_front = CalcNext(m_front);
		return temp;
	}

	/*! \brief Add an element in rear position.

	Add an element in rear position.
	*/
	void Add() noexcept
	{
		++ m_capacity;
		if ( m_rear < m_front )
			++ m_front;
	}

private:
	T m_capacity;  //!< capacity
	T m_front;     //!< front
	T m_rear;      //!< rear
};

// MTreeNodeBase

class MTreeNodeBase
{
protected:
	MTreeNodeBase() noexcept : m_parent(NULL), m_child(NULL), m_child_tail(NULL),
				m_next(NULL), m_prev(NULL), m_child_count(0)
	{
	}
	MTreeNodeBase(const MTreeNodeBase&) = delete;
	~MTreeNodeBase() noexcept
	{
	}

	MTreeNodeBase& operator=(const MTreeNodeBase&) = delete;

	MTreeNodeBase* GetParent() const noexcept
	{
		return m_parent;
	}
	MTreeNodeBase* GetChild() const noexcept
	{
		return m_child;
	}
	MTreeNodeBase* GetChildTail() const noexcept
	{
		return m_child_tail;
	}
	MTreeNodeBase* GetNext() const noexcept
	{
		return m_next;
	}
	MTreeNodeBase* GetPrev() const noexcept
	{
		return m_prev;
	}

	uintptr_t GetCount() const noexcept
	{
		return m_child_count;
	}
	MTreeNodeBase* GetAt(uintptr_t index) const noexcept
	{
		uintptr_t n = 0;
		MTreeNodeBase* pc = m_child;
		while ( pc != NULL ) {
			if ( n == index )
				return pc;
			pc = pc->m_next;
			++ n;
		}
		return NULL;
	}

	uintptr_t Find(MTreeNodeBase* p) const noexcept
	{
		uintptr_t n = 0;
		MTreeNodeBase* pc = m_child;
		if ( pc == NULL )
			return (uintptr_t)-1;
		if ( pc == p )
			return n;
		pc = pc->m_next;
		++ n;
		while ( pc != nullptr ) {
			if ( pc == p )
				return n;
			pc = pc->m_next;
			++ n;
		}
		return (uintptr_t)-1;
	}

	bool IsChild(MTreeNodeBase* p) const noexcept
	{
		return p != NULL && p->m_parent == this;
	}

	void InsertAfter(MTreeNodeBase* p, MTreeNodeBase* pa) noexcept
	{
		assert( p != NULL && (pa == NULL || IsChild(pa)) );
		p->m_parent = this;
		if ( pa == NULL ) {
			p->m_prev = NULL;
			p->m_next = m_child;
			if ( m_child != NULL )
				m_child->m_prev = p;
			m_child = p;
			if ( m_child_tail == NULL )
				m_child_tail = p;
		}
		else {
			p->m_prev = pa;
			p->m_next = pa->m_next;
			pa->m_next = p;
			if ( p->m_next != NULL )
				p->m_next->m_prev = p;
			if ( m_child_tail == pa )
				m_child_tail = p;
		}
		m_child_count ++;
	}
	void Add(MTreeNodeBase* p) noexcept
	{
		InsertAfter(p, m_child_tail);
	}

	bool Remove(MTreeNodeBase* p) noexcept
	{
		if ( p == NULL || !IsChild(p) )
			return false;
		//child
		if ( m_child == p )
			m_child = p->m_next;
		if ( m_child_tail == p )
			m_child_tail = p->m_prev;
		p->m_parent = NULL;
		//next & prev
		if ( p->m_prev != NULL )
			p->m_prev->m_next = p->m_next;
		if ( p->m_next != NULL )
			p->m_next->m_prev = p->m_prev;
		p->m_prev = NULL;
		p->m_next = NULL;
		-- m_child_count;
		return true;
	}

protected:
	MTreeNodeBase* m_parent;
	MTreeNodeBase* m_child;
	MTreeNodeBase* m_child_tail;
	MTreeNodeBase* m_next;
	MTreeNodeBase* m_prev;
	uintptr_t m_child_count;
};

////////////////////////////////////////////////////////////////////////////////
}
////////////////////////////////////////////////////////////////////////////////
#endif
////////////////////////////////////////////////////////////////////////////////
